package 算法.leetcode.offer.lkh;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/combination-sum/solution/zu-he-zong-he-by-leetcode-solution/
 * @author lchenglong
 * @date 2022/4/20
 */
public class LKH39 {

    public static void main(String[] args) {
        LKH39 instance = new LKH39();
        int[] candidates = new int[]{2, 3, 5};
        int target = 8;
        List<List<Integer>> ans = instance.combinationSum(candidates, target);
        System.out.println(Arrays.toString(ans.toArray()));
    }

    List<List<Integer>> ans;


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 返回值
        ans = new ArrayList<>();
        depth(candidates, target, new ArrayList<Integer>(), 0);
        return ans;
    }

    public void depth(int[] candidates, int target, List<Integer> result, int index) {
        if (index == candidates.length) {
            return;
        }
        // 本次结束
        if (target == 0) {
            ans.add(new ArrayList<Integer>(result));
            return;
        }
        // 递归当前元素后面的数组
        depth(candidates,target,result,index+1);
        // 去掉当前节点的递归
        if (target - candidates[index] >= 0) {
            result.add(candidates[index]);
            depth(candidates, target - candidates[index], result, index);
            // 回溯
            result.remove(result.size() - 1);
        }
    }
}
